翻訳と辞書 Words near each other ・ Zig zag (railway) ・ Zig Zag (Tha Mexakinz album) ・ Zig Zag (The Hooters album) ・ Zig Zag (video game) ・ Zig Zag Girl ・ Zig Zag Railway ・ Zig Zag railway station ・ Zig zag revolver ・ Zig Ziglar ・ Zig, Iran ・ Zig-Zag (company) ・ Zig-zag bridge ・ Zig-Zag Chair ・ Zig-zag in-line package ・ Zig-zag lemma ・ Zig-zag product ・ Zig-Zag Walk ・ Zig-Zag! ・ Zig-Zaggin' Through Ghostland ・ Ziga ・ Ziga Department ・ Zigaboo.com ・ Zigadaf ・ Zigadenus ・ Zigaexperientia ・ Zigama Credit and Savings Bank ・ Zigana Pass ・ Zigana Tunnel ・ Zigano ・ Ziganov Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Zig-zag product ： ウィキペディア英語版 Zig-zag product In graph theory, the zig-zag product of regular graphs $G,H$, denoted by $G\; \backslash circ\; H$, takes a large graph ($G$) and a small graph ($H$), and produces a graph that approximately inherits the size of the large one but the degree of the small one. An important property of the zig-zag product is that if $H$ is a good expander, then the expansion of the resulting graph is only slightly worse than the expansion of $G$. Roughly speaking, the zig-zag product $G\; \backslash circ\; H$ replaces each vertex of $G$ with a copy (cloud) of $H$, and connects the vertices by moving a small step (zig) inside a cloud, followed by a big step (zag) between two clouds, and finally performs another small step inside the destination cloud. The zigzag product was introduced by . When the zig-zag product was first introduced, it was used for the explicit construction of constant degree expanders and extractors. Later on the zig-zag product was used in computational complexity theory to prove that symmetric logspace and logspace are equal . ==Definition== Let $G$ be a $D$-regular graph on $()$ with rotation map $\backslash mathrm\_G$ and let $H$ be a $d$-regular graph on $()$ with rotation map $\backslash mathrm\_H$. The zig-zag product $G\; \backslash circ\; H$ is defined to be the $d^$-regular graph on $()\; \backslash times\; ()$ whose rotation map $\backslash mathrm\_$ is as follows: $\backslash mathrm\_((v,a),(i,j))$: # Let $(a\text{'},i\text{'})\; =\; \backslash mathrm\_\; (a,i)$. # Let $(w,b\text{'})=\backslash mathrm\_(v,a\text{'})$. # Let $(b,j\text{'})=\backslash mathrm\_(b\text{'},j)$. # Output $((w,b),(j\text{'},i\text{'}))$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Zig-zag product」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.